import java.util.PriorityQueue;

class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

/**
 * 148. 排序链表
 * https://leetcode.cn/problems/sort-list/description/
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;

        // 1、创建小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        // 2、把链表上所有的节点都放进小根堆里
        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = null;
            heap.offer(cur);
            cur = next;
        }
        // 3、再逐一取出小根堆里的元素
        ListNode ret = new ListNode();
        cur = ret;
        while(!heap.isEmpty()) {
            cur.next = heap.poll();
            cur = cur.next;
        }
        return ret.next;
    }
}